package io.github.hadyang.leetcode.offer;

import io.github.hadyang.leetcode.TreeNode;

/** @author haoyang.shi */
public class BSTKthNode {

  public TreeNode KthNode(TreeNode pRoot, int k) {
    TreeNode[] nodes = new TreeNode[1];

    int[] ints = {0};

    KthNode(pRoot, k, nodes, ints);

    return nodes[0];
  }

  private void KthNode(TreeNode root, int k, TreeNode[] res, int[] cursor) {
    if (root == null) return;

    if (res[0] != null) return;

    KthNode(root.left, k, res, cursor);
    cursor[0]++;

    if (cursor[0] == k) {
      res[0] = root;
      return;
    }

    KthNode(root.right, k, res, cursor);
  }
}
